package _2022.hot100._322_零钱兑换;

import java.util.Arrays;

/**
 * @author： YHSimon
 * @date： 2022-05-29 10:03
 */
// 动态规划 自下而上
public class Solution3 {
    public int coinChange(int[] coins,int amount){
        int max=amount+1;
        int[] dp=new int[amount+1];
        Arrays.fill(dp, max);
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(coins[j]<=i){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}
